package pt.compflow.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * An iterator for Level Order Tree traversal
 *
 */
public class TreeIterator implements Iterator<Tree> {
	
	private List<Tree> list = new ArrayList<Tree>();
	private int pos = 0;

	public TreeIterator(Tree tree) {
		getLevelOrderedList(tree);
	}
	
	private void getLevelOrderedList(Tree tree) {
		
		if(tree.getNode() != null) list.add(tree);
		
		List<Tree> prevList = new ArrayList<Tree>();
		prevList.add(tree);
		
		List<Tree> newList = new ArrayList<Tree>();
		newList.addAll(tree.getChildren());
		
		while(newList.size() > 0) {
			List<Tree> tmpNewList = new ArrayList<Tree>();
			for(Tree subTree : newList) {
				if(subTree.getNode() != null) list.add(subTree);
				tmpNewList.addAll(subTree.getChildren());
			}
			
			prevList = newList;
			newList = tmpNewList;
		} 
	}

	@Override
	public boolean hasNext() {
		return pos < list.size();
	}

	@Override
	public Tree next() {
		Tree node = list.get(pos);
		pos++;
		return node;
	}

	@Override
	public void remove() {
		throw new java.lang.UnsupportedOperationException("Remove not supported.");
	}
}
